#ifndef __HEAP_POLICY__
#define __HEAP_POLICY__

#include "heap_policy.hpp" // declares heap_policy
#include <cmath> // defines ilogb
#include <iostream> // defines std::cerr

extern int ilogb  (double) throw();

template <> template <typename position, typename ordering>
heap_policy<2, position, ordering>::heap_policy (
  heap_policy<2, position, ordering>::index n
): n(n) {
}

template <> template <typename position, typename ordering>
typename heap_policy<2, position, ordering>::index
heap_policy<2, position, ordering>::size () const {
  return n;
}

template <> template <typename position, typename ordering>
typename heap_policy<2, position, ordering>::index
    heap_policy<2, position, ordering>::last_leaf () const {
  return n - 1;
}

template <> template <typename position, typename ordering>
typename heap_policy<2, position, ordering>::index
heap_policy<2, position, ordering>::last_child (
  heap_policy<2, position, ordering>::index i
) const { 
  index k = (i / 7);
  index m = k * 7;
  if((i - m) < 3) return (i << 1) - m + 2;
  else  return (14 * i) - 28 - (42 * k);
}

template <> template <typename position, typename ordering>
typename heap_policy<2, position, ordering>::index
heap_policy<2, position, ordering>::first_child (
  heap_policy<2, position, ordering>::index i
) const {
  index k = (i / 7);
  index m = k * 7;
  if((i - m) < 3) return 2 * i - m + 1;
  else  return (14 * i) - 35 - (42 * k);
}

template <> template <typename position, typename ordering>
typename heap_policy<2, position, ordering>::index
heap_policy<2, position, ordering>::parent (
  heap_policy<2, position, ordering>::index i
) const {
  index j = i / 7;
  if(i != j * 7) return ((i + j * 7 - 1) >> 1);
  else return (j + 6 * ((j - 1) / 8) + 5) >> 1;
}

template <> template <typename position, typename ordering>
typename heap_policy<2, position, ordering>::index
heap_policy<2, position, ordering>::top_some_absent (
  position a,
  heap_policy<2, position, ordering>::index i,
  const ordering& less
) const {
  return first_child(i);  
}

template <> template <typename position, typename ordering>
typename heap_policy<2, position, ordering>::index
heap_policy<2, position, ordering>::top_all_present (
  position a,
  heap_policy<2, position, ordering>::index i,
  const ordering& less
) const {
  typedef typename heap_policy<2, position, ordering>::index index;
  index k = (i / 7);
  index m = k * 7;
  if((i - m) < 3) {
    m = (i << 1) - m + 1;
    k = m + 1;
  }
  else { 
    m = (14 * i) - 35 - (42 * k);  
    k = m + 7;
  }
  return less(a[m], a[k]) ? k : m;    
}

template <> template <typename position, typename ordering>
void
heap_policy<2, position, ordering>::update_some_absent (
  position a,
  heap_policy<2, position, ordering>::index i,
  const heap_policy<2, position, ordering>::element& x,
  const ordering& less
) {
  a[i] = x;
}

template <> template <typename position, typename ordering>
void
heap_policy<2, position, ordering>::update_all_present (
  position a,
  heap_policy<2, position, ordering>::index i,
  const heap_policy<2, position, ordering>::element& x,
  const ordering&
) {
  a[i] = x;
}

template <> template <typename position, typename ordering>
void
heap_policy<2, position, ordering>::visit_branch_first_time (
  position,
  heap_policy<2, position, ordering>::index,
  const ordering&
) {
  // Does nothing
}

template <> template <typename position, typename ordering>
void
heap_policy<2, position, ordering>::erase_last_leaf (position) {
  --n;
}

#endif // __HEAP_POLICY__

